package exp10;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;
    private String valS = "";

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return toString1(this);
    }


    public String toString1(TreeNode bt)    //层次遍历的算法
    {
        Queue<TreeNode> qu = new LinkedList<TreeNode>(); //定义一个队列qu
        qu.offer(bt);                //根结点进队
        while (!qu.isEmpty())        //队不空循环
        {
            TreeNode p = qu.poll();   //出队一个结点
            if (p != null) valS += p.val + ", ";      //访问p结点
            else {
                valS += "null" + ", ";
                continue;
            }
            if (p.left != null)       //有左孩子时将其进队
            {
                qu.offer(p.left);
                if (p.right == null) qu.offer(null);

            }
            if (p.right != null)        //有右孩子时将其进队
            {
                qu.offer(p.right);
                if (p.left == null) qu.offer(null);
            }
        }
        valS = "[" + valS.substring(0, valS.length() - 2) + "]";//去掉最后两位的值
        return valS;
    }
}

class AVLTree {
    TreeNode root;
    String bstr;

    public TreeNode constructTree(Integer[] array) { //层次遍历构建二叉树
        if (array == null || array.length == 0 || array[0] == null) {
            return null;
        }

        int index = 0;
        int length = array.length;

        root = new TreeNode(array[0]);
        Deque<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        TreeNode currNode;
        while (index < length) {
            index++;
            if (index >= length) {
                return root;
            }
            currNode = nodeQueue.poll();
            Integer leftChild = array[index];
            if (leftChild != null) {
                currNode.left = new TreeNode(leftChild);
                nodeQueue.offer(currNode.left);
            }
            index++;
            if (index >= length) {
                return root;
            }
            Integer rightChild = array[index];
            if (rightChild != null) {
                currNode.right = new TreeNode(rightChild);
                nodeQueue.offer(currNode.right);
            }
        }

        return root;
    }
}

class Solution {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

public class BSTValidate {


    public static void main(String[] args) {
        Solution solution = new Solution();
        Integer[] nums = {2, 1, 3};
        AVLTree tree = new AVLTree();
        TreeNode node = tree.constructTree(nums);
        System.out.println(solution.isValidBST(node));

    }
}
